Worms

Memory limit: 32 MB

In the Mysterious Land of Worms there are many worm-houses. Not all of them are inhabited. It is known however, that at most one worm lives in each house. Some pairs of houses are connected with a path. For any pair of two different houses there exists exactly one route consisting of paths, so that none of the paths repeats on the route.

One day, all of the worms decided to meet in one of the houses. They agreed that every hour each of them will move along a path leaving the house it is presently in and will go to the other house at the opposite end of that path (walking along any path in the Mysterious Land of Worms takes exactly one hour). Worms intend to continue their travel untill the moment, when all of them meet in the same house (they need to be in that house exactly in the same time).

Unfortunately, worms have not foreseen that it may take a long period of time to meet if they apply this method of movement. Sometimes it is even impossible to meet. That is why worms asked you for help with verifying whether their meeting can be arranged and if so, how long it will take to meet in the best case.

Task

Write a program which:

• reads the description of the Mysterious Land of Worms from the standard input,
• checks whether the worms can meet and if so, how long it will take in the best case,
• writes the answer to the standard output.

Input

The first line of the standard input contains two integers and (, ), separated with a single space and denoting accordingly the number of houses and the number of paths in the Mysterious Land of Worms. Houses are numbered with natural numbers ranging from to . Following lines contain descriptions of paths. Each of them consists of two integers and (), separated with a single space and denoting numbers of houses connected with a given path. Description of paths is followed by a line containing one integer (), denoting the number of worms living in the Mysterious Land of Worms. Each of the following lines contains one integer () denoting the house where the -th worm lives.

Output

The first and only line of standard output should contain only one word NIE (i.e. no in Polish), if worms cannot meet while moving according to the rules, or one integer equal to the number of hours required by all worms to get to the meeting place.

Example

For the input data:

6 5
1 2
2 3
2 4
4 5
4 6
3
2
5
6

the correct result is:

1

Task author: Jakub Radoszewski.